/*
    动态规划中用观察优化枚举的技巧-下

    前置知识: 
    讲解066 ~ 讲解081 - 动态规划基础
    讲解082 - 动态规划中用观察优化枚举的技巧-上
    【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

    上节课讲了利用严格位置依赖的动态规划来 建立空间感，进而观察并优化枚举
    本节课继续讲述 观察并优化转移方程 来优化枚举（题目1、2）
    同时还要讲述 观察并设计高效的查询结构 来优化枚举（题目3、4）

    注意：
    优化枚举的技巧很多，讲解075-多重背包利用二进制分组、单调队列进行优化，本节课讲根据观察优化
    【必备】课程中的优化手段是笔试、面试最常见的优化类型，此外动态规划的枚举行为还有如下的优化：
    单调栈、树状数组、线段树、预处理表、状态设计优化、单调性优化、斜率优化、四边形不等式 ..等等
    这些内容会在【扩展】、【挺难】课程里安排讲述

    ================================================

    题目1
    规划兼职工作
    你打算利用空闲时间来做兼职工作赚些零花钱，这里有n份兼职工作
    每份工作预计从startTime[i]开始、endTime[i]结束，报酬为profit[i]
    返回可以获得的最大报酬
    注意，时间上出现重叠的 2 份工作不能同时进行
    如果你选择的工作在时间X结束，那么你可以立刻进行在时间X开始的下一份工作
    测试链接 : https://leetcode.cn/problems/maximum-profit-in-job-scheduling/

    利用观察单调性 + 二分搜索的方式优化枚举，最优解时间复杂度O(n*logn)

    ================================================

    题目2
    K个逆序对数组
    逆序对的定义如下：
    对于数组nums的第i个和第j个元素
    如果满足0<=i<j<nums.length 且 nums[i]>nums[j]，则为一个逆序对
    给你两个整数n和k，找出所有包含从1到n的数字
    且恰好拥有k个逆序对的不同的数组的个数
    由于答案可能很大，只需要返回对10^9+7取余的结果
    测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/

    最优解 利用观察 + 构造窗口累加和，已经进入 观察并设计高效的查询结构 的范畴了
    只不过这个结构就仅存在于概念，并用一个int类型的变量维护而已

    ================================================

    题目3
    自由之路
    题目描述比较多，打开链接查看
    测试链接 : https://leetcode.cn/problems/freedom-trail/

    优化枚举的核心是贪心策略：
    下一步做枚举时，不需要枚举所有可能性，只需要枚举 顺时针的最近、逆时针的最近 两种可能性即可

    贪心当然会有专题讲述！【必备】课程的动态规划专题结束了，就会开始贪心的专题

    ================================================

    题目3
    买卖股票的最佳时机 III
    给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
    设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易
    注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票
    测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii

    ================================================

    题目4
    累加和不大于k的最长子数组
    给定一个无序数组arr，长度为n，其中元素可能是正、负、0
    给定一个整数k，求arr所有的子数组中累加和<=k的最长子数组长度
    测试链接 : https://www.nowcoder.com/practice/3473e545d6924077a4f7cbc850408ade

    强烈推荐先看一下讲解046

    利用构造单调数组 + 二分搜索的解不是最优解，时间复杂度O(n*logn)

    最优解中包含的贪心思想（窗口的加速建立、可能性的淘汰），是这个题的重点，时间复杂度O(n)

    贪心当然会有专题讲述！【必备】课程的动态规划专题结束了，就会开始贪心的专题

*/